package com.gozap.sort.spec;

/**
 * 堆排序具体排序算法实现（将数组组成一个二叉树，然后进行最大堆操作，在挨个提取最大值）
 * 
 * 由于词算法涉及到复制数组导致无法使用统一接口
 * 
 * @author yaoming
 * @date 2013-1-4 下午05:07:04
 * @since JDK1.6
 * @version 2.0.0
 */
public class HeapSort {

	public void sort() {
		int len = arr.length;
		int begin = (len - 1) / 2;
		// 组装最大堆 n O(lg n)
		for (int i = begin; i >= 0; i--) {
			maxHeap(arr, i, len - 1);
		}
		// 复制一个新的数组
		int[] copy = new int[len];
		for (int i = 0; i < len; i++) {
			copy[i] = arr[i];
			arr[i] = 0;
		}
		// 从最大堆中挨个取出最大数
		int t = copy[0];

		for (int i = len - 1; i > 0; i--) {
			t = copy[0];
			copy[0] = copy[i];
			copy[i] = t;
			arr[i] = t;
			maxHeap(copy, 0, i - 1);
		}
		arr[0] = copy[0];

	}

	/**
	 * 对下标为i处的数进行最大堆操作
	 * 
	 * @param arr
	 * @param i
	 */
	private void maxHeap(int[] arr, int i, int endIndex) {
		int left = (i + 1) * 2 - 1;
		int right = (i + 1) * 2;

		int largest = i;

		if (right <= endIndex && arr[right] > arr[i]) {
			largest = right;
		}
		if (left <= endIndex && arr[left] > arr[largest]) {
			largest = left;
		}

		if (largest != i) {
			int temp = arr[i];
			arr[i] = arr[largest];
			arr[largest] = temp;

			maxHeap(arr, largest, endIndex);
		}
	}

	static int arr[] = { 4, 5, 3, 9, 8, 7, 98, 72, 10, 12, 8, 6, 20, 15, 60,
			45, 2, 43, 11, 50 };

	public static void print() {
		int len = arr.length;
		for (int i = 0; i < len; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void main(String[] args) {
		HeapSort sort = new HeapSort();
		sort.sort();
		// sort.maxHeap(arr, 0, 2);
		print();
		System.out.println();

		System.out.println("======");
	}
}
